#include <bits/stdc++.h>
using namespace std;

/*
3459. 最长 V 形对角线段的长度
已解答
困难
相关标签
premium lock icon
相关企业
提示
给你一个大小为 n x m 的二维整数矩阵 grid，其中每个元素的值为 0、1 或 2。

V 形对角线段 定义如下：

线段从 1 开始。
后续元素按照以下无限序列的模式排列：2, 0, 2, 0, ...。
该线段：
起始于某个对角方向（左上到右下、右下到左上、右上到左下或左下到右上）。
沿着相同的对角方向继续，保持 序列模式 。
在保持 序列模式 的前提下，最多允许 一次顺时针 90 度转向 另一个对角方向。


返回最长的 V 形对角线段 的 长度 。如果不存在有效的线段，则返回 0。

 

示例 1：

输入： grid = [[2,2,1,2,2],[2,0,2,2,0],[2,0,1,1,0],[1,0,2,2,2],[2,0,0,2,2]]

输出： 5

解释：



最长的 V 形对角线段长度为 5，路径如下：(0,2) → (1,3) → (2,4)，在 (2,4) 处进行 顺时针 90 度转向 ，继续路径为 (3,3) → (4,2)。

示例 2：

输入： grid = [[2,2,2,2,2],[2,0,2,2,0],[2,0,1,1,0],[1,0,2,2,2],[2,0,0,2,2]]

输出： 4

解释：



最长的 V 形对角线段长度为 4，路径如下：(2,3) → (3,2)，在 (3,2) 处进行 顺时针 90 度转向 ，继续路径为 (2,1) → (1,0)。

示例 3：

输入： grid = [[1,2,2,2,2],[2,2,2,2,0],[2,0,0,0,0],[0,0,2,2,2],[2,0,0,2,0]]

输出： 5

解释：



最长的 V 形对角线段长度为 5，路径如下：(0,0) → (1,1) → (2,2) → (3,3) → (4,4)。

示例 4：

输入： grid = [[1]]

输出： 1

解释：

最长的 V 形对角线段长度为 1，路径如下：(0,0)。

 

提示：

n == grid.length
m == grid[i].length
1 <= n, m <= 500
grid[i][j] 的值为 0、1 或 2。
*/

// 法一
class Solution {
public:
    int lenOfVDiagonal(vector<vector<int>>& grid) {
        int n = grid.size();
        if (n == 0)     return 0;
        int m = grid[0].size();
        if (m == 0)     return 0;

        // 四个方向向量
        vector<pair<int, int>> dirs = {{1, 1}, {-1, -1}, {1, -1}, {-1, 1}};
        // 每个方向顺时针旋转90度后的方向索引映射 旋转映射一下
        vector<int> clockwise = {2, 3, 1, 0};

        int maxLen = 0;

        // 可能的起点 遍历
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 从1开始
                if (grid[i][j] != 1) continue;

                // 四个方向
                for (int dis1 = 0; dis1 < 4; dis1++) {
                    // 该路径下的 沿初始方向的有效路径
                    vector<pair<int, int>> path;
                    path.emplace_back(i , j);       // 点加入路径
                    int ci = i, cj = j;
                    int step = 1;       // 步长 看走了几步 判断预期值

                    // 延伸
                    while (true) {
                        int ni = ci + dirs[dis1].first;  // 下一行
                        int nj = cj + dirs[dis1].second; // 下一列
                        if (ni < 0 || ni >= n || nj < 0 || nj >= m) break;  // 越界停止
                        
                        // 步骤1预期2，步骤2预期0，步骤3预期2...以此类推
                        int expected = (step % 2 == 1) ? 2 : 0;
                        if (grid[ni][nj] == expected) {
                            path.emplace_back(ni, nj);
                            ci = ni;
                            cj = nj;
                            step++;
                        } else {
                            break;  // 不符合模式停止延伸
                        }
                    }
                    // 不做旋转变化的最大长度
                    maxLen = max(maxLen, (int)path.size());

                    // 所有都转向试试
                    for (int k = 0; k < path.size(); ++k) {
                        int d2 = clockwise[dis1];  // 转向后的方向
                        int turn_i = path[k].first;
                        int turn_j = path[k].second;
                        int next_step = k + 1;  // 转向后的步骤计数(延续之前的步骤)
                        int turn_length = 0;    // 转向后新增的长度
                        
                        // 沿转向后方向延伸
                        int ni = turn_i + dirs[d2].first;
                        int nj = turn_j + dirs[d2].second;
                        
                        while (true) {
                            if (ni < 0 || ni >= n || nj < 0 || nj >= m) break;
                            
                            // 按步骤判断预期值
                            int expected = (next_step % 2 == 1) ? 2 : 0;
                            if (grid[ni][nj] == expected) {
                                turn_length++;
                                next_step++;
                                // 继续下一个位置
                                turn_i = ni;
                                turn_j = nj;
                                ni += dirs[d2].first;
                                nj += dirs[d2].second;
                            } else {
                                break;
                            }
                        }
                        
                        // 总长度 = 转向点前的长度 + 转向后的长度
                        maxLen = max(maxLen, (k + 1) + turn_length);
                    }
                }
            }
        }
        return maxLen;
    }
};

// 法二
// 记忆数组做了预处理 减少重复计算
class Solution {
public:
    // 定义四个对角方向向量（按顺时针顺序排列）：
    // {1,1}：右下方向（行+1，列+1）
    // {1,-1}：左下方向（行+1，列-1）
    // {-1,-1}：左上方向（行-1，列-1）
    // {-1,1}：右上方向（行-1，列+1）
    static constexpr int DIRS[4][2] = {{1, 1}, {1, -1}, {-1, -1}, {-1, 1}}; 
    int lenOfVDiagonal(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();

        // 预先的记忆数组  位置(i,j)沿方向k不转向时，最长符合模式的路径长度
        // 修正：C++ 需显式指定 vector 完整模板参数（原代码缺失外层模板参数）
        vector<vector<array<int, 4>>> memo(m, vector<array<int, 4>>(n));

        // 修正：C++17 不支持 this auto&& 递归 lambda，需用 std::function 显式声明函数类型
        // 函数签名：(当前i, 当前j, 方向k, 是否允许转向, 目标值) -> 最长路径长度
        function<int(int, int, int, bool, int)> dfs;
        // 递归的DFS Func 从当前位置沿方向k延伸的最长V形线段长度
        dfs = [&](int i, int j, int k, bool can_turn, int target) -> int {
            // 沿着k方向移动一步
            i += DIRS[k][0];
            j += DIRS[k][1];

            // 不延伸的情况 终止 越界或当前位置数值不符合目标值
            if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != target)     return 0;
            // 不转向的情况 就使用记忆数组 避免反复计算了
            if (!can_turn && memo[i][j][k])     return memo[i][j][k];
            // 继续沿当前方向延伸 target切换 step++（递归调用已声明的 dfs 变量）
            int ans = dfs(i, j, k, can_turn, 2 - target) + 1;
            // 不允许转向 结果进数组
            if (!can_turn)  return memo[i][j][k] = ans;

            // 四个方向的最大理论长度   用于剪枝 优化
            int maxs[4] = {m - i, j + 1, i + 1, n - j};
            // 顺时针的旋转 diridx + 1 （mod4）
            k = (k + 1) % 4;
            // 转向后的最大理论长度 当前方向和其对向的最小值 不超过当前的ans 不递归了直接
            if (min(maxs[k], maxs[(k + 3) % 4]) > ans) {
                // 转向后不允许再转（can_turn=false），计算转向后的长度并取最大值
                ans = max(ans, dfs(i, j, k, false, 2 - target) + 1);
            }
            return ans;
        };

        int ans = 0;
        // 遍历矩阵中所有可能的起点（值为1的位置）
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 1) {
                    continue; // 线段必须从1开始
                }
                // 计算四个方向的理论最大长度（从起点沿方向k走到边界的步数）
                int maxs[4] = {m - i, j + 1, i + 1, n - j}; 
                // 尝试四个初始方向
                for (int k = 0; k < 4; k++) { 
                    // 优化：若理论最大长度不超过当前ans，无需递归（剪枝）
                    if (maxs[k] > ans) {
                        // 初始调用：从(i,j)出发，沿方向k，允许转向，第一个目标值为2（1后面必须是2）
                        // 总长度+1是因为包含起点1（修正：显式用 std::max 避免作用域歧义）
                        ans = max(ans, dfs(i, j, k, true, 2) + 1);
                    }
                }
            }
        }
        return ans;
    }
};